In a multitasking environment there is often a requirement to synchronize the execution of various tasks or ensure one process has been completed before another begins. This requirement is facilitated by the use of a software switch known as a semaphore. Specifically, an operating system may implement at least one semaphore to determine an order in which processes are to be executed. The semaphore may be a variable or abstract data type which controls access to a common resource that is used by multiple applications in a parallel programming environment.
A counting semaphore may utilize a counter system for a set of available resources. For example, the counting semaphore may include a count representing a maximum number of resources for processes of the operating system. For each process using a resource, the count may be decremented until no further processes may be allocated a resource. Upon a resource becoming free, the count may be incremented so that the counting semaphore may allocate the freed resource to an application.
Conventional semaphores for an operating system may utilize a lock or non-deterministic atomic operators to isolate the semaphore for a process. However, the locks may result in deadlocks or other impasses that prevent the semaphore from being acquired. For instance, one application may lock a semaphore and then go into an endless loop or otherwise encounter an error. A timeout is enforced when an entity that does not own the semaphore is unable to acquire within a specified amount of time. This may occur under normal conditions, that is, the another entity (or series of entities) may acquire the semaphore and hold it longer than the caller wishes to wait for it to become available. Alternatively, complex lock-free algorithms may be difficult to prove correct which may result in misallocation of resources, bypassing of processes queued for allocation of a resource, etc.
Within these conventional computer systems, there is no known implementation of semaphore timeout for semaphores with lock-free fast paths and message passing backends.